package cn.edu.xjtu.data_structure.chapter02_stack_queue.stack;

/**
 * @author yjq
 * @version 1.0
 * @date 2021/9/11 22:18
 */
public class BracketMatching {
    //利用栈完成括号匹配
    static boolean match(char[]exp){
        char stack[] = new char[exp.length];
        int top=-1;
        for (int i=0;i<exp.length;i++){
            if (exp[i]=='('){
                stack[++top]='(';//遇到'('则入栈
            }
            if (exp[i]==')'){
                if (top==-1){
                    return false;//栈空说明')'比'('多，不匹配
                }else {
                    --top;//栈不空则将栈中的一个'('弹出
                }
            }
        }
        if (top==-1){
            return true;//栈空则说明所有括号都被处理掉
        }
        return false;//否则括号不匹配
    }

    public static void main(String[] args) {
        BracketMatching test = new BracketMatching();
        String string = "((1+1)+(2+1)))";
        char[] exp=string.toCharArray();
        System.out.println(string+"括号匹配: "+test.match(exp));
    }
}
